package com.c2b.algorithm.leetcode.base;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href='https://leetcode.cn/problems/fraction-to-recurring-decimal/'>分数到小数(Fraction to Recurring Decimal)</a>
 * <p>给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。</p>
 * <p>如果小数部分为循环小数，则将循环的部分括在括号内。</p>
 * <p>如果存在多个答案，只需返回 任意一个 。</p>
 * <p>对于所有给定的输入，保证 答案字符串的长度小于 10^4 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：numerator = 1, denominator = 2
 *      输出："0.5"
 *
 * 示例 2：
 *      输入：numerator = 2, denominator = 1
 *      输出："2"
 *
 * 示例 3：
 *      输入：numerator = 4, denominator = 333
 *      输出："0.(012)"
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>-2^31 <= numerator, denominator <= 2^31 - 1</li>
 *     <li>denominator != 0</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/14 16:17
 */
public class LC0166FractionToRecurringDecimal_M {
    static class Solution {

        public String fractionToDecimal(int numerator, int denominator) {
            // 转long计算，防止溢出
            long numeratorLong = numerator;
            long denominatorLong = denominator;
            // 如果本身能够整除，直接返回
            if (numeratorLong % denominatorLong == 0) {
                return String.valueOf(numeratorLong / denominatorLong);
            }
            StringBuilder stringBuilder = new StringBuilder();
            // 如果一个正数、一个负数，则需要先加上负号
            if (numeratorLong < 0 ^ denominatorLong < 0) {
                stringBuilder.append("-");
            }
            numeratorLong = Math.abs(numeratorLong);
            denominatorLong = Math.abs(denominatorLong);
            // 计算整数部分
            stringBuilder.append(numeratorLong / denominatorLong).append(".");
            // 处理小数部分
            Map<Long, Integer> map = new HashMap<>();
            while ((numeratorLong = (numeratorLong % denominatorLong) * 10) != 0 && !map.containsKey(numeratorLong)) {
                // 记录当前余数所在答案的位置，并继续模拟除法运算
                map.put(numeratorLong, stringBuilder.length());
                stringBuilder.append(numeratorLong / denominatorLong);
            }
            // 如果当前余数之前出现过，则将 [出现位置 到 当前位置] 的部分抠出来（循环小数部分）
            if (map.containsKey(numeratorLong)) {
                Integer index = map.get(numeratorLong);
                stringBuilder.insert(index.intValue(), '(').append(')');
            }
            return stringBuilder.toString();
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.fractionToDecimal(4, 333));
        System.out.println(solution.fractionToDecimal(-2147483648, -1));
    }
}
